1. Field of the Invention
The present invention relates generally to digital filters and, more particularly, relates to a partial sum digital FIR filter.
2. Background
In electrical systems, signals of interest are often corrupted by electrical noise and other forms of interference at unwanted frequencies. When this occurs, it is necessary to attenuate or eliminate the corrupting signals from the signal of interest. Electrical filters are used for this purpose. FIG. 1a depicts a basic filter 100. A desired signal 102 and an undesired signal 104 are combined to produce a signal 106 that is input to filter 100. Filter 100 suppresses the undesired signal portion of signal 106 and passes only the desired signal portion 108.
FIGS. 1b-1d illustrate some of the basic forms filters can take. FIG. 1b depicts a low pass filter 110. A desired low frequency signal 112 is combined with an undesired high frequency signal 114 to produce a signal 116 that is input to low pass filter 110. Low pass filter 110 passes only those signals having a frequency below a given cutoff frequency. Hence, filter 110 suppresses the undesired high frequency portion of combined signal 116 and passes only the desired low frequency signal 118.
FIG. 1c shows a high pass filter 120. An undesired low frequency signal 122 is combined with a desired high frequency signal 124 to produce a signal 126 that is input to high pass filter 120. High pass filter 120 passes only those signals having a frequency above a given cutoff. Hence, filter 120 suppresses the undesired low frequency portion of combined signal 126 and passes only the desired high frequency signal 128.
FIG. 1d portrays a bandpass filter 130. Only those signals whose frequencies fall within a given frequency band are passed by filter 130; signals whose frequencies are above or below the passband are attenuated. In this case, three signals 132, 134 and 136 are combined to produce a signal 138 that is input to bandpass filter 130. Signal 132 has a frequency below the passband of filter 130; signal 134 has a frequency within the passband of filter 130; and signal 136 has a frequency above the passband of filter 130. Hence, filter 130 suppresses the high and low frequency portions 132 and 134 of signal 138 and outputs a signal 139 containing only the signal 134 within the filter passband.
The filters of FIGS. 1a-1d have traditionally been implemented using analog electric components such as resistors, capacitors and operational amplifiers. The signal being filtered is an electrical voltage or current corresponding to a physical quantity, such as a sound or video signal. Analog filters, while useful for many purposes, have several associated drawbacks. Since an analog filter is implemented by analog circuitry components, it can be changed only by redesigning or replacing the circuitry components. Moreover, the performance of analog filters, particularly those implemented with analog components, is typically temperature-dependent and subject to drift.
Advances in digital technology have led to the design and implementation of digital filters. Computer programs and/or processors can filter digital signals in the same way that analog filters filter analog signals. A digital filter is typically implemented as software or code running on a processor or controller to perform numerical calculations on sampled values of a signal. The processor may be a general-purpose microprocessor such as a PC microprocessor, or it may be a specialized DSP (Digital Signal Processor) chip. The high computational speeds possible with DSPs make them ideal candidates for implementation of digital filters. Alternatively, a digital filter can be implemented in digital logic hardware. Such hardware configurations can be dedicated or configurable, such as with a PAL or GAL. Digital filters have several advantages over analog filters. As software or code residing in the processor""s memory determines the operation of a digital filter, the filter is programmable and can be easily changed or redesigned without changes in the circuitry or hardware. Digital filters are also more stable than analog filters and do not generally suffer from time and temperature induced variations.
A commonly used type of digital filter is a finite impulse response (FIR) filter. Each output of a FIR filter is the sum of a finite number of weighted samples of the input sequence. FIR filters are sometimes also referred to as feed-forward or non-recursive filters since all paths lead forward from the input to the output; no part of the filter output is fed back to the filter input. A common application of digital FIR filters is in video encoders for filtering or scaling input video signals from sources such as computers into forms suitable for display on devices such as television monitors.
A block diagram of a conventional FIR filter 150 is set forth in FIG. 2a. Filter 150, as do most FIR filters, comprises three basic building blocks: unit delays (152, 154, 156); multipliers (162, 164, 166, 168); and adders (172, 174, 176). Input samples x[n] supplied to filter 150 are advanced through unit delays 152, 154 and 156. Typically, each unit delay imposes a delay of one clock cycle. Hence, on a clock cycle where the input sample is x[n], delay 152 outputs the previous input sample x[nxe2x88x921]; delay 154 outputs the second previous input sample x[nxe2x88x922]; and delay 156 outputs the third previous input sample x[nxe2x88x923]. In a hardware or DSP implementation of a unit delay, an input sample value is stored in memory for one clock cycle and then released to the output. In filter 150, for example, delays 152, 154 and 156 may be implemented as three memory cells configured as a shift register.
The input sample x[n] and delayed samples x[nxe2x88x921] . . . x[nxe2x88x923] are input to multipliers 162-168 and multiplied by filter coefficients a[0] . . . a[3]. A FIR filter is said to comprise a xe2x80x9ctapxe2x80x9d for each input sample, i.e., x[n] . . . x[nxe2x88x923], and each filter coefficient is referred to as a xe2x80x9ctap coefficientxe2x80x9d. Even if some the tap coefficients are xe2x80x9c0xe2x80x9d, the filter is still said to comprise the same number of taps as there are input signals. Hence, filter 150 is a 4-tap filter even if some of coefficients a[0] . . . a[3] are xe2x80x9c0xe2x80x9d. The values of filter coefficients a[0]-a[3] determine the response and characteristics of filter 150, that is, the coefficient values determine the filter gain and frequency response. In a video encoder implementation, the coefficient values will determine the scaling and filtering performed on input data samples. From a mathematical standpoint, computation of the filter coefficients is often the most difficult and complex part of filter design. Several approaches for coefficient generation are familiar to those of ordinary skill in the art. Examples include the Fourier Series method, the Frequency Sampling method and the Remez Exchange Method.
The multiplied or weighted outputs of multipliers 162 . . . 168 are summed by adders 172 . . . 176. The outputy[n] of filter 150, then, can be expressed as:
y[n]=a[0]x[n]+a[1]x[nxe2x88x921]+a[2]x[nxe2x88x922]+a[3]x[nxe2x88x923].
More generally speaking, the output y[n] of an M+1 tap filter can be expressed as:       y    ⁡          [      n      ]        =            ∑              k        =        0            M        ⁢                  a        k            ⁢                        x          ⁡                      [                          n              -              k                        ]                          .            
Hence, each output sample can be described as the current weighted input sample added to a predetermined number of previous and variously weighted input samples.
FIG. 2b illustrates a filter 180 that is an alternative implementation of filter 150 of FIG. 2a. Filter 180 is a 4-tap filter and generates an output y[n] that is the same as the output y[n] of filter 150. Line stores 182 . . . 186 perform the same function as delay elements 152 . . . 156, except they store adjacent sequences of samples, or lines, as opposed to consecutive samples. Therefore, line stores 182-186 store an input sample and generate an output sample on each clock cycle, and the outputs of line stores 182-186 are delayed one line relative to their inputs. Multiplier 188 multiplies an input sample by a coefficient a[0], multiplier 190 multiplies the corresponding sample from the previous line (i.e., the output sample of line store 182) by a coefficient a[1], multiplier 192 multiplies the corresponding sample from the second previous line by a coefficient a[2], and multiplier 194 multiplies the corresponding sample from the third previous line by a coefficient a[3]. Adder 196 performs the function of adders 172 . . . 176 of filter 150 and generates an output       y    ⁡          [      n      ]        =            ∑              k        =        0            M        ⁢                  a        k            ⁢                        x          ⁡                      [                          n              -              k                        ]                          .            
In video signal filtering and scaling applications, filters such as filters 150 and 180 are often inadequate for smoothing out significant variations that may occur from input line to input line. This is especially important for video applications where the display is interlaced. As illustrated in FIG. 2c, a second filter 198 may be employed to address this problem. The output y[n] of filter 180 is supplied to line store (delay element) 191 of filter 198 and to multiplier 193. Multiplier 193 multiplies the current filter output y[n] by a first smoothing coefficient i[0], and multiplier 195 multiplies the previous filter output y[nxe2x88x921] output by line store 191 by a second smoothing coefficient i[1]. The smoothing coefficients are chosen or calculated to attenuate any large variations between adjacent output lines. The outputs of multipliers 193 and 195 are summed by adder 197 to generate a smoothed output z[n].
Among the basic components of a FIR filter, the multiplier is the most complex and costliest to implement. Moreover, the operational speed of conventional implementations of multipliers is relatively slow and imposes a fundamental limit on the speed and throughput of the filter. Conventional FIR filters such as filters 150 and 180 suffer from the drawback of using a large number of multipliers. Additionally, conventional FIR filters are often inadequate for smoothing large variations between proximate input samples. Where an additional filter such as filter 198 of FIG. 2c is used to address this problem, the number of multipliers is further increased as is the number of line stores required.
The present invention provides a partial sum digital FIR filter that uses a reduced number of multipliers and provides enhanced smoothing of large variations between proximate input data samples. The FIR filter produces partial sums of previous input samples that are provided to an adaptive filter controller. The adaptive filter controller uses the partial sums and the current input sample to detect and smooth large variations between adjacent samples.
In one embodiment of the invention, a digital FIR filter is provided that inputs a series of data samples x[0] . . . x[n] and generates a partial sum output PS[i], where ixe2x89xa6n. The partial sum output comprises a weighted version of the a difference between a partial sum of the previous ixe2x88x921 data samples, PS[ixe2x88x921], and the current data sample x[n] added to the current data sample x[n]. The filter includes a plurality of weighting stages. Each weighting stage includes a first adder for subtracting the current data sample x[n] from the previous partial sum PS[ixe2x88x921], a multiplier that multiplies the difference by a weighting coefficient, and a second adder that sums the weighted difference with the current data sample. The filter also includes a plurality of delay elements, each of which inputs a partial sum and imposes a unit delay on the partial sum before supplying it to a weighting stage.
Further features and advantages of this invention as well as the structure of operation of various embodiments are described in detail below with reference to the accompanying drawings.